#include<vector>
#include<unordered_map>
#include<iostream>
using std::unordered_map;
using std::vector;


class Solution {
private:
    unordered_map<int, int> mp0, mp1;
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int n = nums.size();
        if (nums[0]) mp1 = {{nums[0], 1}, {-nums[0], 1}};
        else mp1 = {{0, 2}};
        for (int i = 1; i < n; i++) {
            int val = nums[i];
            // std::cout << "mp1: ";
            // for (auto& p: mp1) std::cout << "(" << p.first << "," << p.second << ") ";
            // std::cout << "\n"; 
            mp0 = mp1;
            mp1 = {};
            
            for (auto& p: mp0) {
                
                insert(p.first+val, p.second);
                insert(p.first-val, p.second);
            }
        }
        return (mp1.find(target) == mp1.end()) ? 0 : mp1[target];
    }

    void insert(int val, int count) {
        if (mp1.find(val) == mp1.end()) mp1[val] = count;
        else mp1[val] += count;
    }

    
};